import java.util.LinkedList;
import java.util.Queue;

/**
 * 200. Number Of Islands 岛屿数量
 * https://leetcode.cn/problems/number-of-islands/description/
 */
class NumberOfIslands {
    /**
     * 方法：使用深度优先搜索（DFS）遍历网格，遇到'1'时进行岛屿计数，并通过DFS标记所有相连的陆地
     * 
     * Args:
     *   grid: char[][] - 由'0'（水）和'1'（陆地）组成的二维网格
     * 
     * Returns:
     *   int - 岛屿的数量
     * 
     * Time: O(M*N) - 需要遍历整个网格，M和N分别是网格的行数和列数
     * Space: O(M*N) - 递归调用栈的深度，最坏情况下可能需要遍历整个网格
     */
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    count ++;
                    dfs(i, j, grid);
                }
            }
        }
        return count;
    }

    private void dfs(int i, int j, char[][] grid){
        int m = grid.length, n = grid[0].length;
        // 出界，或者不是 '1'，就不再往下递归
        if(i < 0 || i >= m || j < 0 || j>= n || grid[i][j] != '1'){
            return;
        }
        grid[i][j] = '2';  //插旗！避免来回横跳无限递归
        // 往四个方向递归
        dfs(i, j - 1, grid);
        dfs(i, j + 1, grid);
        dfs(i - 1, j, grid);
        dfs(i + 1, j, grid);
    }

    /**
     * 方法：使用广度优先搜索（BFS）遍历网格，遇到'1'时进行岛屿计数，并通过BFS标记所有相连的陆地
     * 
     * Args:
     *   grid: char[][] - 由'0'（水）和'1'（陆地）组成的二维网格
     * 
     * Returns:
     *   int - 岛屿的数量
     * 
     * Time: O(M*N) - 需要遍历整个网格，M和N分别是网格的行数和列数
     * Space: O(min(M,N)) - 队列在最坏情况下可能存储对角线上的所有元素
     */
    public int numIslands1(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;
        int[][] directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    count ++;
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{i, j});
                    grid[i][j] = '2';
                    while(!queue.isEmpty()){
                        int cur[] = queue.poll();
                        for(int[] d: directions){
                            int x = cur[0] + d[0];
                            int y = cur[1] + d[1];
                            if(0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '1'){
                                grid[x][y] = '2';
                                queue.offer(new int[]{x, y});
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
}